package algorithm.tanxin;

import java.util.Comparator;
import java.util.PriorityQueue;

public class IPO {

    public static class Program{
        public int p;
        public int c;

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o1.c - o2.c;
            }
        });
        PriorityQueue<Program> maxProfit = new PriorityQueue<>(new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o2.p - o1.p;
            }
        });

        for (int i = 0; i < Capital.length; i++) {
            minCostQ.add(new Program(Profits[i], Capital[i]));
        }

        for (int i = 0; i < K; i++) {
            while(!minCostQ.isEmpty() && minCostQ.peek().c <= W){
                maxProfit.add(minCostQ.poll());
            }

            if(maxProfit.isEmpty()){
                return W;
            }

            W += maxProfit.poll().p;
        }
        return W;

    }


}
